{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Greatest Value in Each Row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #sorting #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #排序 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteGreatestValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除每行中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 大小的矩阵 <code>grid</code> ，由若干正整数组成。</p>\n",
    "\n",
    "<p>执行下述操作，直到 <code>grid</code> 变为空矩阵：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。</li>\n",
    "\t<li>将删除元素中的最大值与答案相加。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong> 每执行一次操作，矩阵中列的数据就会减 1 。</p>\n",
    "\n",
    "<p>返回执行上述操作后的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/19/q1ex1.jpg\" style=\"width: 600px; height: 135px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,4],[3,3,1]]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>上图展示在每一步中需要移除的值。\n",
    "- 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们可以删除任一）。在答案上加 4 。\n",
    "- 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。\n",
    "- 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。\n",
    "最终，答案 = 4 + 3 + 1 = 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/19/q1ex2.jpg\" style=\"width: 83px; height: 83px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[10]]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>上图展示在每一步中需要移除的值。\n",
    "- 在第一步操作中，从第一行删除 10 。在答案上加 10 。\n",
    "最终，答案 = 10 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-greatest-value-in-each-row](https://leetcode.cn/problems/delete-greatest-value-in-each-row/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-greatest-value-in-each-row](https://leetcode.cn/problems/delete-greatest-value-in-each-row/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,4],[3,3,1]]', '[[10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(map(max,zip(*grid)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        for i in range(m):\n",
    "            grid[i].sort()\n",
    "        \n",
    "        for j in range(n):\n",
    "            maxn = float('-inf')\n",
    "            for i in range(m):\n",
    "                maxn = max(maxn, grid[i][j])\n",
    "            \n",
    "            res += maxn\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        res = 0\n",
    "        while grid[0]:\n",
    "            temp = []\n",
    "            for i in grid:\n",
    "                temp.append(i.pop())\n",
    "            res += max(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        # 求和优化 \n",
    "        return sum(map(max, zip(*list(sorted(i) for i in grid))))\n",
    "\n",
    "        # basic\n",
    "        z = list(zip(*list(sorted(i) for i in grid)))\n",
    "        print(z)\n",
    "        res = 0\n",
    "        for i in z:\n",
    "            res += max(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)) :\n",
    "            grid[i].sort()\n",
    "\n",
    "        for i in range(len(grid[0])) :\n",
    "            newArray = [ ]\n",
    "            for j in range(len(grid)) :\n",
    "                newArray.append(grid[j][i])\n",
    "\n",
    "            ans += max(newArray)\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "\n",
    "        return sum(map(max,zip(*grid)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        #会用到内置函数zip\n",
    "        #zip接收若干个迭代器，将里面的元素变成元组对并返回一个列表\n",
    "        res=0#初始化结果值\n",
    "        for i in grid:\n",
    "            i.sort()#将子列表分别进行排序\n",
    "        for j in zip(*grid):#解压\n",
    "            res+=max(j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for ro in grid:\n",
    "            ro.sort()\n",
    "        return sum (map(max,zip(*grid)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        new_grid = [sorted(line) for line in grid]\n",
    "        return sum([max(i) for i in zip(*new_grid)])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i)for i in zip(*grid)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "\n",
    "        return sum(map(max,zip(*grid)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        dillist = []\n",
    "        result = 0\n",
    "        for times in range(0,len(grid[0])):\n",
    "            for row in range(0,len(grid)):\n",
    "                dillist.append(grid[row].pop(grid[row].index(max(grid[row]))))\n",
    "            result += max(dillist)\n",
    "            dillist = []\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(map(max, zip(*grid)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            grid[i].sort(reverse = True)\n",
    "        grid = [[row[i] for row in grid] for i in range(len(grid[0]))]\n",
    "        return sum(max(i) for i in grid)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(m):\n",
    "                max_ =  max(grid[j])\n",
    "                index = grid[j].index(max_)\n",
    "                tmp = max(tmp, max_)\n",
    "                grid[j][index] = -1\n",
    "            res += tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        \n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        for i in zip(*grid):\n",
    "            ans+=max(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        Max = 0\n",
    "        ans = 0\n",
    "\n",
    "        for _ in range(len(grid[0])):\n",
    "            for x in grid:\n",
    "                # return max(x)\n",
    "                Max = max(max(x), Max)\n",
    "                x.remove(max(x))\n",
    "            ans += Max\n",
    "            Max = 0\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "            n = len(i)\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        for k in range(0,n):\n",
    "            for j in grid:\n",
    "                res = max(res,j[k])\n",
    "            ans += res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(max(col) for col in zip(*grid))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        grid = list(map(sorted, grid))\n",
    "        ans = 0\n",
    "        for j in range(len(grid[0]) - 1, -1, -1):\n",
    "            ans += max(grid[i][j] for i in range(len(grid)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        return sum(max(col) for col in zip(*(sorted(col) for col in grid)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            grid[i].sort()\n",
    "        for j in range(len(grid[i])):\n",
    "            ans += max(grid[i][j] for i in range(len(grid)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sum=0\n",
    "        y=x=[]\n",
    "        if len(grid)==1:\n",
    "            for z in grid[0]:\n",
    "                sum+=z\n",
    "        else:\n",
    "            for j in range(len(grid[0])):\n",
    "                for i in grid:\n",
    "                    i.sort()\n",
    "                    y.append(i.pop())\n",
    "                    if len(y)==len(grid):\n",
    "                        sum+=max(y)\n",
    "                        y=[]\n",
    "        return sum         \n",
    "\n",
    "       \n",
    "        \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for l in grid:\n",
    "            l.sort()\n",
    "        return sum(max(l) for l in zip(*grid))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        k = len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        while k > 0:\n",
    "            tmp = []\n",
    "            for x in range(len(grid)):\n",
    "                max_ = max(grid[x])\n",
    "                tmp.append(max_)\n",
    "                grid[x].remove(max_)\n",
    "            ans += max(tmp)\n",
    "            k -= 1\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sums=0\n",
    "        while grid[0]!=[]:\n",
    "            Max=0\n",
    "            for t,i in enumerate(grid):\n",
    "                now=max(i)\n",
    "                Max=max(now,Max)\n",
    "                grid[t].remove(now)\n",
    "            else:\n",
    "                sums+=Max\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sum=0\n",
    "        y=x=[]\n",
    "        if len(grid)==1:\n",
    "            for z in grid[0]:\n",
    "                sum+=z\n",
    "        else:\n",
    "            for j in range(len(grid[0])):\n",
    "                for i in grid:\n",
    "                    i.sort()\n",
    "                    y.append(i.pop())\n",
    "                    if len(y)==len(grid):\n",
    "                        sum+=max(y)\n",
    "                        y=[]\n",
    "        return sum         \n",
    "\n",
    "       \n",
    "        \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        max_value = 0\n",
    "        answer = 0\n",
    "        while len(grid[0]) > 0:\n",
    "            for i in grid:\n",
    "                m = max(i)\n",
    "                if m > max_value:\n",
    "                    max_value = m\n",
    "                i.remove(m)\n",
    "            answer += max_value\n",
    "            max_value = 0\n",
    "        return answer\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        result = 0\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        for j in range(n):\n",
    "            a = []\n",
    "            for m in grid:\n",
    "                a.append(m[-1])\n",
    "                m.pop()\n",
    "            result = result + max(a)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        grid=zip(*grid)\n",
    "        n=0\n",
    "        for i in grid:\n",
    "            n+=max(i)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        #会用到内置函数zip\n",
    "        #zip接收若干个迭代器，将里面的元素变成元组对并返回一个列表\n",
    "        res=0#初始化结果值\n",
    "        for i in grid:\n",
    "            i.sort()#将子列表分别进行排序\n",
    "        for j in zip(*grid):#解压\n",
    "            res+=max(j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        array = []\n",
    "        for row in grid:\n",
    "            array.append(sorted(row, reverse=True))\n",
    "        for row in zip(*array):\n",
    "            ans += max(row)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        a,b=m,n\n",
    "        ans=0\n",
    "        while a>0 and b>0:\n",
    "            current=0\n",
    "            for i in range(m):\n",
    "                cc=0\n",
    "                cur_idx=0\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]>=cc:\n",
    "                        cc=grid[i][j]\n",
    "                        cur_idx=j\n",
    "                current=max(current,grid[i][cur_idx])\n",
    "                grid[i][cur_idx]=0\n",
    "            ans+=current\n",
    "            b-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        for j in zip(*grid):\n",
    "            res += max(j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        lm = len(grid)\n",
    "        ans = 0\n",
    "        for item in grid:\n",
    "            item.sort(reverse=True)\n",
    "        for j in range(len(item)):\n",
    "            ans += max([grid[i][j] for i in range(lm)])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        return sum(max(list(map(sorted, grid))[i][j] for i in range(len(grid))) for j in range(len(grid[0]) -1 , -1, -1)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for row in grid:\n",
    "            row.sort()\n",
    "        return sum(map(max, zip(*grid))) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for _ in range(n):\n",
    "            tmp = []\n",
    "            for i in range(m):\n",
    "                ma = max(grid[i])\n",
    "                tmp.append(ma)\n",
    "                grid[i].remove(ma)\n",
    "            res+=max(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(m):\n",
    "                a = max(grid[j])\n",
    "                ind = grid[j].index(a)\n",
    "                t.append(a)\n",
    "                grid[j].pop(ind)\n",
    "            ans += max(t)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        n , m = len(grid) , len(grid[0])\n",
    "        for row in grid :\n",
    "            row.sort(reverse=True)\n",
    "        ans = 0 \n",
    "        for col in zip(*grid):\n",
    "            ans += max(col)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def deleteGreatestValue(self, grid: list[list[int]]) -> int:\r\n",
    "        he = 0\r\n",
    "        #排序\r\n",
    "        for i in range(len(grid)):\r\n",
    "            grid[i] = sorted(grid[i])\r\n",
    "        print(grid)\r\n",
    "        #转置\r\n",
    "        grid = list(map(list,zip(*grid)))\r\n",
    "        print(grid)\r\n",
    "        #加最大\r\n",
    "        for i in range(len(grid)):\r\n",
    "            he += max(grid[i])\r\n",
    "        return he\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sums=0\n",
    "        while len(grid[0])>0:\n",
    "            res=[]\n",
    "            for i in range(len(grid)):\n",
    "                res.append(max(grid[i]))\n",
    "                grid[i].remove(max(grid[i]))\n",
    "            sums+=max(res)\n",
    "\n",
    "        return sums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        ans = 0\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for j in range(m):\n",
    "            tmp = grid[0][j]\n",
    "            for i in range(n):\n",
    "                tmp = max(grid[i][j], tmp)\n",
    "            ans += tmp\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        r = 0\n",
    "        l = len(grid[0])\n",
    "        for i in range(l):\n",
    "            t = 0\n",
    "            for j in grid:\n",
    "                m = max(j)\n",
    "                j.remove(m)\n",
    "                if m > t:\n",
    "                    t = m\n",
    "            r += t\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sums=0\n",
    "        while grid[0]!=[]:\n",
    "            Max=0\n",
    "            for t,i in enumerate(grid):\n",
    "                now=max(i)\n",
    "                Max=max(now,Max)\n",
    "                grid[t].remove(now)\n",
    "            else:\n",
    "                sums+=Max\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        grid = [sorted(each, reverse=True) for each in grid]\n",
    "        z = 0\n",
    "        for i in range(len(grid[0])):\n",
    "            a = 0\n",
    "            for j in range(len(grid)):\n",
    "                a = max(grid[j][i], a)\n",
    "            z += a\n",
    "        return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            grid[i].sort()\n",
    "\n",
    "        for j in range(n):\n",
    "            tmp = grid[0][j]\n",
    "            for i in range(m):\n",
    "                tmp = max(tmp, grid[i][j])\n",
    "            res += tmp\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i in grid:\n",
    "            i.sort()\n",
    "        return sum([max(i) for i in zip(*grid)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        array = [sorted(row, reverse=True) for row in grid]\n",
    "        for row in zip(*array):\n",
    "            ans += max(row)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        # paixu\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(len(grid)):\n",
    "            grid[i].sort(reverse=True)\n",
    "        print(grid)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            max_n = 0\n",
    "            for i in range(m):\n",
    "                max_n = max(max_n,grid[i][j])\n",
    "            ans += max_n\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        a = 0\n",
    "        while grid[0]:\n",
    "            n = len(grid)\n",
    "            l = []\n",
    "            print('----')\n",
    "            for i in range(n):\n",
    "                print(grid[i])\n",
    "                max_ = max(grid[i])\n",
    "                l.append(max_)\n",
    "                grid[i].remove(max_)\n",
    "            a += max(l)\n",
    "        return a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        sums=0\n",
    "        while grid[0]!=[]:\n",
    "            Max=0\n",
    "            for t,i in enumerate(grid):\n",
    "                now=max(i)\n",
    "                Max=max(now,Max)\n",
    "                grid[t].remove(now)\n",
    "            else:\n",
    "                sums+=Max\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        # 当grid中还有值时\n",
    "        while grid:\n",
    "            # 存储每一行的最大值\n",
    "            max_vals = []\n",
    "            for i in range(len(grid)):\n",
    "                max_val = max(grid[i])\n",
    "                max_vals.append(max_val)\n",
    "                grid[i].remove(max_val)\n",
    "                \n",
    "            # 从所有最大值中取出最大的\n",
    "            res += max(max_vals)\n",
    "            \n",
    "            # 删除空行\n",
    "            grid = [row for row in grid if row]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        q_all= [PriorityQueue() for _ in range(len(grid))]\n",
    "        for i,line in enumerate(grid):\n",
    "            for x in line:\n",
    "                q_all[i].put(-x)\n",
    "        res = 0\n",
    "        while q_all[0].empty()==False:\n",
    "            del_q=PriorityQueue()\n",
    "            for i in range(len(grid)):\n",
    "                del_q.put(q_all[i].get())\n",
    "            res=res+abs(del_q.get())\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ret = 0\n",
    "        all_max = []\n",
    "        for _ in range(n):\n",
    "            for i in range(m):\n",
    "                row_max = max(grid[i])\n",
    "                all_max.append(row_max)\n",
    "                grid[i].remove(row_max)\n",
    "            ret += max(all_max)\n",
    "            all_max = []\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        grid=[sorted(i,key=lambda x:-x) for i in grid]\n",
    "        grid=[max(i) for i in zip(*grid) ]\n",
    "        return sum(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        q_all=[PriorityQueue()for _ in range(len(grid))]\n",
    "        for i,line in enumerate(grid):\n",
    "            for x in line:\n",
    "                q_all[i].put(-x)\n",
    "        res=0\n",
    "        while q_all[0].empty()==False:\n",
    "            del_q=PriorityQueue()\n",
    "            for i in range(len(grid)):\n",
    "                del_q.put(q_all[i].get())\n",
    "            res=res+abs(del_q.get())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int: \n",
    "\n",
    "        # 取每一行的最大值 --> 取每一列的最大值 \n",
    "\n",
    "        # 对每一行进行排序 \n",
    "        for row in grid: \n",
    "            row.sort() \n",
    "    \n",
    "        # 遍历：\n",
    "        res = 0 \n",
    "        for i in range(len(grid[0])):   # 外层，遍历小数组 \n",
    "            print('1: ', i, grid[0][i])\n",
    "            col_max = grid[0][i]        # 初始化每一列的最大值 \n",
    "            for j in range(len(grid)):  # 内层，遍历大数组 \n",
    "                print('2: ', j, grid[j][i])\n",
    "                col_max = max(col_max, grid[j][i])    # 每一列的最大值 \n",
    "                print('3: ', col_max)\n",
    "            res += col_max \n",
    "        \n",
    "        return res\n",
    "\n",
    "        ''' \n",
    "        这道题同2679. 矩阵中的和\n",
    "        这道题的操作总共分两步：\n",
    "\n",
    "        取出每一行的最大值；\n",
    "        在取出最大值中再选出一个最大值，加入分数；\n",
    "        删除这些最大值；\n",
    "        循环这些操作直到所有元素被删除\n",
    "\n",
    "        作者：lxk1203\n",
    "        链接：https://leetcode.cn/problems/delete-greatest-value-in-each-row/solution/javapython3cdui-xing-pai-xu-dui-lie-qu-z-95gx/ \n",
    "\n",
    "        我们将题目给出大小为 m×n 的矩阵 grid 每一行从小到大排序，那么题目等价于每次删除矩阵的末尾列，得分为该列的最大值。\n",
    "        那么最后的答案就是每一列的最大值之和。\n",
    "\n",
    "        作者：LeetCode-Solution\n",
    "        链接：https://leetcode.cn/problems/delete-greatest-value-in-each-row/solution/shan-chu-mei-xing-zhong-de-zui-da-zhi-by-6fh9/\n",
    "        ''' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\r\n",
    "        # # 55/55 cases passed (88 ms)\r\n",
    "        # # Your runtime beats 59.72 % of python3 submissions\r\n",
    "        # # Your memory usage beats 5.55 % of python3 submissions (16.3 MB)\r\n",
    "        # i, output, current_max = 0, 0, 0\r\n",
    "        # while True:\r\n",
    "        #     if len(grid[i]) == 0:\r\n",
    "        #         break\r\n",
    "        #     grid[i] = sorted(grid[i])\r\n",
    "        #     current_max = max(current_max,grid[i][-1])\r\n",
    "        #     grid[i].pop(-1)\r\n",
    "        #     i+=1\r\n",
    "        #     if i == len(grid):\r\n",
    "        #         output += current_max\r\n",
    "        #         current_max = 0\r\n",
    "        #         i = 0\r\n",
    "        # return output\r\n",
    "\r\n",
    "        # 55/55 cases passed (48 ms)\r\n",
    "        # Your runtime beats 81.48 % of python3 submissions\r\n",
    "        # Your memory usage beats 47.22 % of python3 submissions (16.1 MB)\r\n",
    "        sorted_grid = [sorted(l) for l in grid]\r\n",
    "        transpose_grid = list(zip(*sorted_grid))  # 实现列表矩阵转置\r\n",
    "        return sum(map(max, transpose_grid))\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ngrid=[sorted(i) for i in grid]\n",
    "        ngrid=[list(i) for i in zip(*ngrid)]\n",
    "        ngrid=[sorted(i) for i in ngrid]\n",
    "        ngrid=[list(i) for i in zip(*ngrid)]\n",
    "        return sum(ngrid[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        t = []\n",
    "        for i in range(m):\n",
    "            g = Counter(grid[i])\n",
    "            g = sorted(g.items(), key=lambda x:x[0])\n",
    "            tmp = []\n",
    "            for a, b in g:\n",
    "                tmp.append([a, b])\n",
    "            t.append(tmp)\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(m):\n",
    "                a, b = t[j][-1][0], t[j][-1][1]\n",
    "                tmp = max(a, tmp)\n",
    "                if b == 1:\n",
    "                    t[j].pop()\n",
    "                else:\n",
    "                    t[j][-1][1] -= 1\n",
    "            ans += tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\r\n",
    "        grid = [sorted(line) for line in grid]\r\n",
    "        new_grid = [[0]*len(grid) for i in range(len(grid[0]))]\r\n",
    "        for i in range(len(grid)):\r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                new_grid[j][i] = grid[i][j]\r\n",
    "        new_grid = [sorted(line) for line in new_grid]\r\n",
    "        return sum([item[-1] for item in new_grid])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\r\n",
    "        # # 55/55 cases passed (88 ms)\r\n",
    "        # # Your runtime beats 59.72 % of python3 submissions\r\n",
    "        # # Your memory usage beats 5.55 % of python3 submissions (16.3 MB)\r\n",
    "        # i, output, current_max = 0, 0, 0\r\n",
    "        # while True:\r\n",
    "        #     if len(grid[i]) == 0:\r\n",
    "        #         break\r\n",
    "        #     grid[i] = sorted(grid[i])\r\n",
    "        #     current_max = max(current_max,grid[i][-1])\r\n",
    "        #     grid[i].pop(-1)\r\n",
    "        #     i+=1\r\n",
    "        #     if i == len(grid):\r\n",
    "        #         output += current_max\r\n",
    "        #         current_max = 0\r\n",
    "        #         i = 0\r\n",
    "        # return output\r\n",
    "\r\n",
    "        # 55/55 cases passed (48 ms)\r\n",
    "        # Your runtime beats 81.48 % of python3 submissions\r\n",
    "        # Your memory usage beats 47.22 % of python3 submissions (16.1 MB)\r\n",
    "        sorted_grid = [sorted(l) for l in grid]\r\n",
    "        transpose_grid = list(zip(*sorted_grid))  # 实现列表矩阵转置\r\n",
    "        return sum(map(max, transpose_grid))\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        q_all=[PriorityQueue()for _ in range(len(grid))]\n",
    "        for i,line in enumerate(grid):\n",
    "            for x in line:\n",
    "                q_all[i].put(-x)\n",
    "        res=0\n",
    "        while q_all[0].empty()==False:\n",
    "            del_q=PriorityQueue()\n",
    "            for i in range(len(grid)):\n",
    "                del_q.put(q_all[i].get())\n",
    "            res=res+abs(del_q.get())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        tmp, ret = [], 0\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        tmpG = grid[::]\n",
    "        while r > 0:\n",
    "            print(r, c, )\n",
    "            curIterMax = 0\n",
    "            nextG = []\n",
    "            for i in range(r):\n",
    "                curRowMax = max(tmpG[i])\n",
    "                existMaxFlag = False\n",
    "                rowNum = []\n",
    "                for j in range(c):\n",
    "                    if tmpG[i][j] == curRowMax and not existMaxFlag:\n",
    "                        existMaxFlag = True\n",
    "                        continue\n",
    "                    else:\n",
    "                        rowNum.append(tmpG[i][j])\n",
    "                if rowNum:\n",
    "                    nextG.append(rowNum[::])\n",
    "                # cur iter max num\n",
    "                curIterMax = max(curIterMax, curRowMax)\n",
    "            ret += curIterMax\n",
    "            if nextG:\n",
    "                r, c = len(nextG), len(nextG[0])\n",
    "                tmpG = nextG[::]\n",
    "            else:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        for i, row in enumerate(grid):\n",
    "            row.sort(reverse=True)\n",
    "        print(grid)\n",
    "        grid = list(zip(*grid))\n",
    "        print(grid)\n",
    "        sum_ = 0\n",
    "        for row in grid:\n",
    "            sum_ += max(row)\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteGreatestValue(self, grid: List[List[int]]) -> int:\n",
    "        grid=[sorted(i,key=lambda x:-x) for i in grid]\n",
    "        grid=[max(i) for i in zip(*grid) ]\n",
    "        return sum(grid)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
